/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @author zhong
 *
 */
public class CountDifferentPalindromicSubsequences {
	int mod = 1000000007;

	/**
	 * 
	 * @param S
	 *            只含有a，b，c，d四个字符
	 * @return
	 */
	public int countPalindromicSubsequences(String S) {
		ArrayList<Integer>[] indexes = new ArrayList[4];
		for (int i = 0; i < 4; i++) {
			indexes[i] = new ArrayList<>();
		}
		int n = S.length();
		for (int i = 0; i < S.length(); i++) {
			indexes[S.charAt(i) - 'a'].add(i);
		}

		int[][] dp = new int[n][n];
		return helper(dp, S, indexes, 0, n - 1);
	}

	private int helper(int[][] dp, String s, ArrayList<Integer>[] indexes, int i, int j) {
		if (i > j) {
			return 0;
		}
		if (dp[i][j] != 0) {
			return dp[i][j];
		}
		int ans = 0;
		for (int k = 0; k < indexes.length; k++) {
			int iStart = Collections.binarySearch(indexes[k], i);
			int iEnd = Collections.binarySearch(indexes[k], j);
			// 找iStart后面的第一个，如果i或者j刚好等于，则就是i或j
			// 找iEnd前面的第一个
			if (iStart < 0) {
				iStart = -iStart - 1;
			} else {
				// iStart++;
			}
			if (iEnd < 0) {
				iEnd = -iEnd - 2;
			} else {
				// iEnd--;
			}
			if (iStart == indexes[k].size()) {// 到了最后一个
				continue;
			}
			iStart = indexes[k].get(iStart);
			if (iStart > j) {// i和j之间没有这个
				continue;
			}
			iEnd = indexes[k].get(iEnd);
			ans++;
			if (iStart != iEnd) {
				ans++;
			}
			ans += helper(dp, s, indexes, iStart + 1, iEnd - 1);
			ans %= mod;
		}
		dp[i][j] = ans;
		return ans;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String string = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba";
		System.out.println(new CountDifferentPalindromicSubsequences().countPalindromicSubsequences(string));
	}

}
